package main

import (
	"fmt"
	"time"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		fmt.Println("return")
		return nil
	}
	//先去中间的数
	count := len(nums)
	fmt.Println("count", count)
	rootVal := count / 2
	fmt.Println("rootVal", rootVal)
	fmt.Println(nums[rootVal])

	var root TreeNode
	root.Val = nums[rootVal]
	fmt.Println(root.Val)

	fmt.Println("(nums[:rootVal]) ", (nums[:rootVal]))
	fmt.Println()
	left := sortedArrayToBST(nums[:rootVal])
	root.Left = left
	fmt.Println("(nums[rootVal-1:]) ", (nums[rootVal+1:]))
	right := sortedArrayToBST(nums[rootVal+1:])
	root.Right = right

	return &root
}

func main() {
	start := time.Now()
	nums := []int{-10, -3, 0, 5, 9}

	dec := sortedArrayToBST(nums)
	cost := time.Since(start)
	fmt.Println(dec)
	fmt.Println(cost)
}
